import java.util.*;

public class Bag01 {

    /**
     * 动态规划求解01背包问题
     * @author ShakeJ
     * @date 2024/1/1
     */

    public static void main(String[] args) {
        int[] weight = {1,1,3,4}; //商品自身的重量
        int[] value = {15,15,20,30}; //商品的价值
        int bagSize = 4; //背包的容量
        int res = testWeightBagProblem(weight, value, bagSize);
        System.out.println("可装入背包里物品价值总和最大为：" + res);

//        //自定义测试输入
//        Scanner in=new Scanner(System.in);
//        System.out.print("输入背包的容量：");
//        int b=in.nextInt();
//        System.out.print("输入商品的个数：");
//        int n=in.nextInt();
//        // 商品数组和对应的价值数组长度一样
//        int []w=new int[n];
//        int []v=new int[n];
//
//        System.out.print("依次输入商品的自身重量：");
//        for(int i=0;i<n;i++){
//            w[i]=in.nextInt();
//        }
//
//        System.out.print("依次输入商品的价值：");
//        for(int i=0;i<n;i++) {
//            v[i] = in.nextInt();
//        }
//
//        System.out.println("可装入背包里物品价值总和最大为："+testWeightBagProblem(w,v,b));

    }
    /**
     * 动态规划01背包的问题
     * @param weight
     * @param value
     * @param bagSize
     */
    public static int testWeightBagProblem(int[] weight,int []value,int bagSize){
        // 首先创建dp数组
        int count=weight.length; //获取商品的数量

        // 定义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
        int[][] dp=new int[count-1 +1][bagSize + 1]; //bagSize可以达到，不需要-1操作

        // 定义选取的背包数组
        int[][]path=new int[count][bagSize+1];
        for (int i = 0; i < count; i++) {
            Arrays.fill(path[i], -1);
        }

        for(int i=0;i<count;i++){
            dp[i][0]=0;
        }
        // 创建数组后，需要进行初始化操作
        // 默认的值即为0
        for(int i=weight[0];i<=bagSize;i++){
            dp[0][i]=value[0];
        }

        //对dp数组进行填充
        for(int i=1;i<= weight.length-1;i++){
            for(int j=1;j<=bagSize;j++){
                if(j< weight[i]){
                    /*
                       如果此时的背包容量没有物品的重量大的时候，不放此时的物品i
                       此时的前i-1个物品的最大值几位当前情况的最大值
                     */
                    dp[i][j]=dp[i-1][j];
                }else{
                    /*
                      当前的背包容量可以放下物品i，此时存在两种情况需要判断：
                      1. 不放物品i
                      2. 放物品i
                      两种情况选择最大的即可
                     */
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j- weight[i]]+ value[i]);
                    path[i][j] = i;
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        int m = count-1, n = bagSize;
        while (m >= 0 && n >= 0) {
            if (path[m][n] != -1) {
                result.add(path[m][n]);
                n -= weight[path[m][n]];
            }
            m--;
        }
        Collections.reverse(result);
        System.out.println("选取的物品下标为：");
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();


        // 打印dp数组
        for (int i = 0; i <count; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }


        // 最后返回的是下标即可
        return dp[count-1][bagSize];
    }
}
